#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run23.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/5 0005 16:33
"""
"""
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
"""


class Solution:
    def PermutationHelper(self, chars, begin, result):
        if begin == len(chars) - 1:
            result.add("".join(chars))
        else:
            for j in range(begin, len(chars)):
                if j == begin or chars[j] != chars[begin]:
                    self.swap(chars, begin, j)
                    self.PermutationHelper(chars, begin + 1, list)
                    self.swap(chars, begin, j)

    def Permutation(self, ss):
        result = set()
        if ss.strip() is None:
            return result
        chars = []
        chars.extend(ss)
        temp = set()
        self.PermutationHelper(chars, 0, temp)
        return sorted(result | temp)

    def swap(self, x, a, b):
        x[a], x[b] = x[b], x[a]
